/*

    utils.cpp - implementation of utility functions
    Author Julio Agustin Barrera Mendoza
    Copyright (C) 2010 CINVESTAV-IPN.

    This program is free software; you can redistribute it and/or modify it 
    under the terms of the GNU General Public License as published by 
    the Free Software Foundation; either version 2 of the License, 
    or (at your option) any later version.

    This program is distributed in the hope that it will be useful, 
    but WITHOUT ANY WARRANTY; without even the implied warranty of 
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 
    General Public License for more details.

    You should have received a copy of the GNU General Public License along 
    with this program;  if not, write to the 
    Free Software Foundation, Inc., 59 Temple Place, 
    Suite 330, Boston, MA 02111-1307 USA

 */

#include "utils.h"

// ------------------------------------------------------------------
// FUNCTION Bentley
// ------------------------------------------------------------------

vector<Array> Bentley(const vector<Array> &points)
{
  unsigned int i, j, t, limit = points.size();
  vector<unsigned int> nondominates;
  vector<Array> result;

  nondominates.push_back(0);

  for (i = 1; i < limit; i++)
    {
      j = 0;
      while (j < nondominates.size())
        {
          if (points[nondominates[j]] <= points[i])
            {
              t = nondominates[j];
              nondominates[j] = nondominates[0];
              nondominates[0] = t;
              j = nondominates.size() + 1;
            }
          else if (points[i] <= points[nondominates[j]])
            nondominates.erase(nondominates.begin() + j);
          else
            j++;
        }

      if (j == nondominates.size())
        nondominates.push_back(i);
    }

  limit = nondominates.size();
  for (i = 0; i < limit; i++)
    result.push_back(points[nondominates[i]]);

  return result;
}
